<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="E3HBq" id="E3HBq"><span data-lake-id="ud79579ce" id="ud79579ce">典型回答</span></h1>
  <h2 data-lake-id="j0ens" id="j0ens"><span data-lake-id="u9d1b6978" id="u9d1b6978">为什么是2^n</span></h2>
  <p data-lake-id="udfa642e8" id="udfa642e8"><span data-lake-id="uf9365a97" id="uf9365a97">HashMap是通过</span><code data-lake-id="u23f51b5d" id="u23f51b5d"><span data-lake-id="ue878a4be" id="ue878a4be">(table.length - 1) &amp; (key.hashCode ^ (key.hashCode &gt;&gt; 16))</span></code><span data-lake-id="u4ed5d518" id="u4ed5d518">定位tableIndex的。</span></p>
  <p data-lake-id="u6188d4ad" id="u6188d4ad"><span data-lake-id="uaa6ca562" id="uaa6ca562">​</span><br></p>
  <p data-lake-id="u96e90ac6" id="u96e90ac6"><span data-lake-id="ubd9e3f38" id="ubd9e3f38">为什么是用&amp;而不是用%呢？因为&amp;是基于内存的二进制直接运算，比转成十进制的取模快的多。又因为</span><code data-lake-id="ua167beb3" id="ua167beb3"><span data-lake-id="u3695feac" id="u3695feac">X % 2^n = X &amp; (2^n – 1)</span></code><span data-lake-id="u3829cfec" id="u3829cfec">，可以把%运算转换为&amp;运算。所以，hashMap的</span><span data-lake-id="ua497271b" id="ua497271b" class="lake-fontsize-12" style="color: rgb(85, 85, 85)">capacity</span><span data-lake-id="uc19a35e9" id="uc19a35e9">一定要是2^n。这样，HashMap计算hash的速度才够快</span></p>
  <p data-lake-id="u03c731d4" id="u03c731d4"><span data-lake-id="u57350f19" id="u57350f19">​</span><br></p>
  <p data-lake-id="ub8bb60e2" id="ub8bb60e2"><strong><span data-lake-id="u17948526" id="u17948526">为什么</span></strong><code data-lake-id="u98c8454f" id="u98c8454f"><strong><span data-lake-id="uda967008" id="uda967008">X % 2^n = X &amp; (2^n – 1)</span></strong></code><strong><span data-lake-id="ufc23a0c1" id="ufc23a0c1">？</span></strong></p>
  <p data-lake-id="ub3f71ce4" id="ub3f71ce4"><strong><span data-lake-id="u29fbf38c" id="u29fbf38c">​</span></strong><br></p>
  <p data-lake-id="u148246fe" id="u148246fe"><span data-lake-id="u4a415750" id="u4a415750">假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。</span></p>
  <p data-lake-id="ucd7a4209" id="ucd7a4209"><span data-lake-id="u740b1fa3" id="u740b1fa3">​</span><br></p>
  <p data-lake-id="u4b58e2dc" id="u4b58e2dc"><span data-lake-id="u38d6f272" id="u38d6f272">此时X &amp; (2^3 – 1) 就相当于取X的2进制的最后三位数。</span></p>
  <p data-lake-id="u7f171c07" id="u7f171c07"><span data-lake-id="u55567d8e" id="u55567d8e">​</span><br></p>
  <p data-lake-id="uc9072020" id="uc9072020"><span data-lake-id="u02db32e8" id="u02db32e8">从2进制角度来看，X / 8相当于 X &gt;&gt; 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。</span></p>
  <p data-lake-id="u90fdcac8" id="u90fdcac8"><span data-lake-id="uea2e05ba" id="uea2e05ba">​</span><br></p>
  <p data-lake-id="ueef32bbb" id="ueef32bbb"><span data-lake-id="u892149e1" id="u892149e1">上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。</span></p>
  <p data-lake-id="u81ad9264" id="u81ad9264"><span data-lake-id="ub2e1a3f8" id="ub2e1a3f8">​</span><br></p>
  <p data-lake-id="u371cdc33" id="u371cdc33"><span data-lake-id="u68db3d57" id="u68db3d57">如： 6 % 8 = 6 ，6 &amp; 7 = 6 10 % 8 = 2 ，10 &amp; 7 = 2</span></p>
  <p data-lake-id="ub5a7975f" id="ub5a7975f"><span data-lake-id="u9ca7619f" id="u9ca7619f">​</span><br></p>
  <h2 data-lake-id="pqihD" id="pqihD"><span data-lake-id="u3655ff26" id="u3655ff26">如何保证</span></h2>
  <p data-lake-id="u3b9dc3a5" id="u3b9dc3a5"><span data-lake-id="ud18a2eca" id="ud18a2eca">要想保证HashMap的容量始终是2^n次方，需要在Map初始化的时候，和扩容的时候分别保证</span></p>
  <p data-lake-id="uc55429b1" id="uc55429b1"><span data-lake-id="u814c98ca" id="u814c98ca">​</span><br></p>
  <h3 data-lake-id="ZUUgt" id="ZUUgt"><span data-lake-id="u9d4e6c53" id="u9d4e6c53">初始化时期保证</span></h3>
  <p data-lake-id="u1c860b11" id="u1c860b11" style="text-align: justify"><span data-lake-id="ua65e2d73" id="ua65e2d73" class="lake-fontsize-12" style="color: rgb(85, 85, 85)">当我们通过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。(1-&gt;1、3-&gt;4、7-&gt;8、9-&gt;16)</span></p>
  <p data-lake-id="ufa628c2e" id="ufa628c2e" style="text-align: justify"><span data-lake-id="u3ebcde31" id="u3ebcde31" class="lake-fontsize-12" style="color: rgb(85, 85, 85)">​</span><br></p>
  <blockquote data-lake-id="u023b2ff4" id="u023b2ff4">
   <p data-lake-id="uc442d0dc" id="uc442d0dc" style="text-align: justify"><span data-lake-id="uca585380" id="uca585380">在JDK 1.7和JDK 1.8中，HashMap初始化这个容量的时机不同。JDK 1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在JDK 1.7中，要等到第一次put操作时才进行这一操作。</span></p>
  </blockquote>
  <p data-lake-id="u23b3659e" id="u23b3659e"><br></p>
  <p data-lake-id="u13db888b" id="u13db888b" style="text-align: justify"><span data-lake-id="ufb15013a" id="ufb15013a">看一下JDK是如何找到比传入的指定值大的第一个2的幂的：</span></p>
  <pre lang="java"><code>
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n &gt;&gt;&gt; 1;
    n |= n &gt;&gt;&gt; 2;
    n |= n &gt;&gt;&gt; 4;
    n |= n &gt;&gt;&gt; 8;
    n |= n &gt;&gt;&gt; 16;
    return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
</code></pre>
  <p data-lake-id="u197e95b4" id="u197e95b4"><br></p>
  <p data-lake-id="ufd60cdb7" id="ufd60cdb7" style="text-align: justify"><span data-lake-id="u6a7af57c" id="u6a7af57c">上面的算法目的挺简单，就是：根据用户传入的容量值（代码中的cap），通过计算，得到第一个比他大的2的幂并返回。</span></p>
  <p data-lake-id="u1f7e5d0a" id="u1f7e5d0a" style="text-align: justify"><span data-lake-id="u06815334" id="u06815334">​</span><br></p>
  <p data-lake-id="ud46fbc9a" id="ud46fbc9a" style="text-align: justify"><img src="https://cdn.nlark.com/yuque/0/2022/jpeg/719664/1668839424702-a03b79f5-bcf1-45c3-9151-9308d8d0ead1.jpeg?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_19%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ud5b51bb2" id="ud5b51bb2" style="text-align: justify"><br></p>
  <p data-lake-id="u7a6c5ab8" id="u7a6c5ab8"><span data-lake-id="u0b3368c7" id="u0b3368c7">请关注上面的几个例子中，蓝色字体部分的变化情况，或许你会发现些规律。5-&gt;8、9-&gt;16、19-&gt;32、37-&gt;64都是主要经过了两个阶段。</span></p>
  <p data-lake-id="u821cf6bf" id="u821cf6bf"><span data-lake-id="u33b87331" id="u33b87331">​</span><br></p>
  <blockquote data-lake-id="u5b8d6427" id="u5b8d6427">
   <p data-lake-id="u0bfc95d5" id="u0bfc95d5"><span data-lake-id="u929aa4ff" id="u929aa4ff">Step 1，5-&gt;7</span></p>
   <p data-lake-id="u910cec34" id="u910cec34"><span data-lake-id="uc502689b" id="uc502689b">Step 2，7-&gt;8</span></p>
   <p data-lake-id="u93c19f32" id="u93c19f32"><span data-lake-id="u1427a77c" id="u1427a77c">Step 1，9-&gt;15</span></p>
   <p data-lake-id="u2327bb1d" id="u2327bb1d"><span data-lake-id="u25862ea4" id="u25862ea4">Step 2，15-&gt;16</span></p>
   <p data-lake-id="u997ea462" id="u997ea462"><span data-lake-id="u8c2b9de9" id="u8c2b9de9">Step 1，19-&gt;31</span></p>
   <p data-lake-id="u93313e97" id="u93313e97"><span data-lake-id="u6c98a841" id="u6c98a841">Step 2，31-&gt;32</span></p>
   <p data-lake-id="u3176abc4" id="u3176abc4"><span data-lake-id="uc69fb995" id="uc69fb995">​</span><br></p>
  </blockquote>
  <p data-lake-id="ub37fa31a" id="ub37fa31a"><span data-lake-id="u6b5f56ca" id="u6b5f56ca">对应到以上代码中，Step1：</span></p>
  <p data-lake-id="u11ab7bb6" id="u11ab7bb6"><span data-lake-id="u71934a35" id="u71934a35">​</span><br></p>
  <pre lang="java"><code>
n |= n &gt;&gt;&gt; 1; 
n |= n &gt;&gt;&gt; 2; 
n |= n &gt;&gt;&gt; 4; 
n |= n &gt;&gt;&gt; 8; 
n |= n &gt;&gt;&gt; 16;
</code></pre>
  <p data-lake-id="udb35bd79" id="udb35bd79"><br></p>
  <p data-lake-id="u9066a49e" id="u9066a49e"><span data-lake-id="u50c88f2c" id="u50c88f2c">对应到以上代码中，Step2：</span></p>
  <p data-lake-id="u39fe3f02" id="u39fe3f02"><span data-lake-id="u7e13b3e0" id="u7e13b3e0">​</span><br></p>
  <pre lang="java"><code>
return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
</code></pre>
  <p data-lake-id="u9abb34e6" id="u9abb34e6"><span data-lake-id="u35d8d65d" id="u35d8d65d">Step 2 比较简单，就是做一下极限值的判断，然后把Step 1得到的数值+1。</span></p>
  <p data-lake-id="u0fb4ba11" id="u0fb4ba11"><span data-lake-id="u471c8752" id="u471c8752">​</span><br></p>
  <p data-lake-id="u80e08263" id="u80e08263"><span data-lake-id="ubd4595b3" id="ubd4595b3">Step 1 怎么理解呢？其实是对一个二进制数依次无符号右移，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。</span></p>
  <p data-lake-id="ub707cbb6" id="ub707cbb6"><span data-lake-id="u9a21cb49" id="u9a21cb49">​</span><br></p>
  <p data-lake-id="u8f4d7fab" id="u8f4d7fab"><span data-lake-id="ufd111927" id="ufd111927">因为cap是int类型的，所以最多需要右移16位即可获取其最大值。</span></p>
  <p data-lake-id="u5e7f8ca5" id="u5e7f8ca5"><span data-lake-id="u55fdec18" id="u55fdec18">​</span><br></p>
  <p data-lake-id="u1c95b98a" id="u1c95b98a"><span data-lake-id="u7636b573" id="u7636b573">随便拿一个二进制数，套一遍上面的公式就发现其目的了：</span></p>
  <pre lang="java"><code>
1100 1100 1100 &gt;&gt;&gt;1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 &gt;&gt;&gt;2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 &gt;&gt;&gt;4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
</code></pre>
  <p data-lake-id="ue7f74a18" id="ue7f74a18"><span data-lake-id="u11c98087" id="u11c98087">通过几次无符号右移和按位或运算，我们把1100 1100 1100转换成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，这就是大于1100 1100 1100的第一个2的幂。</span></p>
  <p data-lake-id="u581d3603" id="u581d3603"><span data-lake-id="u9173d8fe" id="u9173d8fe">​</span><br></p>
  <p data-lake-id="uc6501324" id="uc6501324"><span data-lake-id="uea9820ba" id="uea9820ba">好了，我们现在解释清楚了Step 1和Step 2的代码。就是可以把一个数转化成第一个比他自身大的2的幂。</span></p>
  <p data-lake-id="u4c5c8bd4" id="u4c5c8bd4"><span data-lake-id="u70a64b09" id="u70a64b09">​</span><br></p>
  <p data-lake-id="u13b52a3b" id="u13b52a3b"><strong><span data-lake-id="ud3b6f9e6" id="ud3b6f9e6">但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果cap=4套用公式的话。得到的会是 8，不过其实这个问题也被解决了，重点就在</span></strong><code data-lake-id="u261a57e9" id="u261a57e9"><strong><span data-lake-id="u6324f9d9" id="u6324f9d9">int n = cap - 1;</span></strong></code><strong><span data-lake-id="uf42a7800" id="uf42a7800">这行代码中，HashMap会事先将用户给定的容量-1，这样就不会出现上述问题了</span></strong></p>
  <p data-lake-id="u444636a3" id="u444636a3"><strong><span data-lake-id="ua1f97c29" id="ua1f97c29">​</span></strong><br></p>
  <p data-lake-id="u3ea3007f" id="u3ea3007f"><span data-lake-id="uf3132e7d" id="uf3132e7d">总之，HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。</span></p>
  <h3 data-lake-id="g7X6q" id="g7X6q"><span data-lake-id="ue95d0727" id="ue95d0727">扩容时期保证</span></h3>
  <p data-lake-id="u82b3beff" id="u82b3beff"><span data-lake-id="u13c07b8d" id="u13c07b8d">除了初始化的时候回指定HashMap的容量，在进行扩容的时候，其容量也可能会改变。</span></p>
  <p data-lake-id="u4010a319" id="u4010a319"><span data-lake-id="ueb81466f" id="ueb81466f">​</span><br></p>
  <p data-lake-id="u36f53dc4" id="u36f53dc4"><span data-lake-id="ud739bc2f" id="ud739bc2f">HashMap有扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容。</span></p>
  <p data-lake-id="uaa05bde7" id="uaa05bde7"><span data-lake-id="ua18e7592" id="ua18e7592">​</span><br></p>
  <p data-lake-id="u87dbb79e" id="u87dbb79e"><span data-lake-id="u684fbb72" id="u684fbb72">在HashMap中，</span><code data-lake-id="u04523c9a" id="u04523c9a"><span data-lake-id="u71e99344" id="u71e99344">threshold = loadFactor * capacity</span></code><span data-lake-id="u2929d9cd" id="u2929d9cd">。</span></p>
  <p data-lake-id="ue89d54f3" id="ue89d54f3"><span data-lake-id="u527335d1" id="u527335d1">​</span><br></p>
  <p data-lake-id="u74fa0302" id="u74fa0302"><span data-lake-id="uf1e92b2c" id="uf1e92b2c">loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。</span></p>
  <p data-lake-id="u6fb3d1f5" id="u6fb3d1f5"><span data-lake-id="u21cefec0" id="u21cefec0">​</span><br></p>
  <p data-lake-id="u542d2d26" id="u542d2d26"><span data-lake-id="u8569ff3a" id="u8569ff3a">对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。</span></p>
  <p data-lake-id="u5bfb888a" id="u5bfb888a"><span data-lake-id="u1332ab5f" id="u1332ab5f">​</span><br></p>
  <p data-lake-id="u27798036" id="u27798036"><span data-lake-id="ufb978283" id="ufb978283">下面是HashMap中的扩容方法(resize)中的一段：</span></p>
  <pre lang="java"><code>
if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;
                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr &lt;&lt; 1; // double threshold
}
</code></pre>
  <p data-lake-id="u038ebcfc" id="u038ebcfc"><span data-lake-id="uea4d644a" id="uea4d644a">因为oldThr已经是2^n了，所以oldThr无符号左移之后，是oldThr * 2，自然也是2^n。至于后续HashMap是如何扩容的，请听下回分解～</span></p>
  <p data-lake-id="u7af1189b" id="u7af1189b"><span data-lake-id="ue6e40ed9" id="ue6e40ed9">​</span><br></p>
  <h1 data-lake-id="cGbSv" id="cGbSv"><span data-lake-id="ub4a9439f" id="ub4a9439f">知识扩展</span></h1>
  <h2 data-lake-id="lB6Bx" id="lB6Bx"><span data-lake-id="uc0efd7ad" id="uc0efd7ad">负载因子和容量有什么关系?</span></h2>
  <p data-lake-id="u21cbe33e" id="u21cbe33e"><br></p>
  <p data-lake-id="uafa66a0a" id="uafa66a0a"><span data-lake-id="ufa487197" id="ufa487197">HashMap中有几个属性，如capacity记录了HashMap中table的length，size记录了HashMap中KV的对数，threshold记录了扩容的阈值（=loadFactor*capacity），loadFactor则是负载因子，一般是3/4</span></p>
  <p data-lake-id="u537bb5d6" id="u537bb5d6"><span data-lake-id="u91a844da" id="u91a844da">​</span><br></p>
  <p data-lake-id="u75192606" id="u75192606"><strong><span data-lake-id="u0919ddc2" id="u0919ddc2">当HashMap刚刚初始化的时候，如果不指定容量，那么threshold默认是16，如果指定，则默认是第一个比指定的容量大的2的幂（如上文所说），此时size=0，capacity=threshold=16，loadfactor默认是0.75F</span></strong></p>
  <p data-lake-id="u2e83d246" id="u2e83d246"><span data-lake-id="uf8249515" id="uf8249515">​</span><br></p>
  <p data-lake-id="u0a1a7eca" id="u0a1a7eca"><span data-lake-id="ueca34ab9" id="ueca34ab9">当HashMap开始装载的时候（即调用#put方法），那么size=KV的对数，capacity=16暂时不变，threashold=12（loadfactor*capacity），loadfactor=0.75F</span></p>
  <p data-lake-id="ued0e68e2" id="ued0e68e2"><span data-lake-id="u65f213a3" id="u65f213a3">​</span><br></p>
  <p data-lake-id="u4048e42c" id="u4048e42c"><span data-lake-id="u9602e440" id="u9602e440">当HashMap中的size &gt; 12（threashold）时，capacity=32（16 &lt;&lt; 1），threashold=24（loadfactor*capacity），loadfactor=0.75F</span></p>
  <p data-lake-id="u723a5d95" id="u723a5d95"><span data-lake-id="u71001871" id="u71001871">​</span><br></p>
  <p data-lake-id="ucb8b168a" id="ucb8b168a"><span data-lake-id="udc08d0e5" id="udc08d0e5">由此可得，负载因子决定了什么时候扩容，也间接的决定了HashMap中容量的多少</span></p>
  <p data-lake-id="udfdf9360" id="udfdf9360"><span data-lake-id="u3ccfee3d" id="u3ccfee3d">​</span><br></p>
  <h3 data-lake-id="TXyot" id="TXyot"><span data-lake-id="u838e5dd8" id="u838e5dd8">loadfactor为啥默认是0.75F，不是1呢？</span></h3>
  <h2 data-lake-id="GiwTe" id="GiwTe"><span data-lake-id="u70a9867e" id="u70a9867e">HashMap的初始值设为多少合适？</span></h2>
 </body>
</html>